/*
 * Copyright 2013 Google Inc.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package com.aplink.generic.google.maps;

import java.util.List;

import com.google.android.gms.maps.model.LatLng;

public class SphericalUtil {

    /**
     * Returns the angle between two LatLngs, in radians. This is the same as
     * the distance on the unit sphere.
     */
    static double computeAngleBetween(final LatLng from, final LatLng to) {
        return SphericalUtil.distanceRadians(Math.toRadians(from.latitude),
                Math.toRadians(from.longitude), Math.toRadians(to.latitude),
                Math.toRadians(to.longitude));
    }

    /**
     * Returns the area of a closed path on Earth.
     * 
     * @param path
     *            A closed path.
     * @return The path's area in square meters.
     */
    public static double computeArea(final List<LatLng> path) {
        return Math.abs(SphericalUtil.computeSignedArea(path));
    }

    /**
     * Returns the distance between two LatLngs, in meters.
     */
    public static double computeDistanceBetween(final LatLng from,
            final LatLng to) {
        return SphericalUtil.computeAngleBetween(from, to)
                * MathUtil.EARTH_RADIUS;
    }

    /**
     * Returns the heading from one LatLng to another LatLng. Headings are
     * expressed in degrees clockwise from North within the range [-180,180).
     * 
     * @return The heading in degrees clockwise from north.
     */
    public static double computeHeading(final LatLng from, final LatLng to) {
        // http://williams.best.vwh.net/avform.htm#Crs
        final double fromLat = Math.toRadians(from.latitude);
        final double fromLng = Math.toRadians(from.longitude);
        final double toLat = Math.toRadians(to.latitude);
        final double toLng = Math.toRadians(to.longitude);
        final double dLng = toLng - fromLng;
        final double heading = Math
                .atan2(Math.sin(dLng) * Math.cos(toLat),
                        (Math.cos(fromLat) * Math.sin(toLat))
                                - (Math.sin(fromLat) * Math.cos(toLat) * Math
                                        .cos(dLng)));
        return SphericalUtil.wrap(Math.toDegrees(heading), -180, 180);
    }

    /**
     * Returns the length of the given path, in meters, on Earth.
     */
    public static double computeLength(final List<LatLng> path) {
        if (path.size() < 2) {
            return 0;
        }
        double length = 0;
        final LatLng prev = path.get(0);
        double prevLat = Math.toRadians(prev.latitude);
        double prevLng = Math.toRadians(prev.longitude);
        for (final LatLng point : path) {
            final double lat = Math.toRadians(point.latitude);
            final double lng = Math.toRadians(point.longitude);
            length += SphericalUtil.distanceRadians(prevLat, prevLng, lat, lng);
            prevLat = lat;
            prevLng = lng;
        }
        return length * MathUtil.EARTH_RADIUS;
    }

    /**
     * Returns the LatLng resulting from moving a distance from an origin in the
     * specified heading (expressed in degrees clockwise from north).
     * 
     * @param from
     *            The LatLng from which to start.
     * @param distance
     *            The distance to travel.
     * @param heading
     *            The heading in degrees clockwise from north.
     */
    public static LatLng computeOffset(final LatLng from, double distance,
            double heading) {
        distance /= MathUtil.EARTH_RADIUS;
        heading = Math.toRadians(heading);
        // http://williams.best.vwh.net/avform.htm#LL
        final double fromLat = Math.toRadians(from.latitude);
        final double fromLng = Math.toRadians(from.longitude);
        final double cosDistance = Math.cos(distance);
        final double sinDistance = Math.sin(distance);
        final double sinFromLat = Math.sin(fromLat);
        final double cosFromLat = Math.cos(fromLat);
        final double sinLat = (cosDistance * sinFromLat)
                + (sinDistance * cosFromLat * Math.cos(heading));
        final double dLng = Math.atan2(
                sinDistance * cosFromLat * Math.sin(heading), cosDistance
                        - (sinFromLat * sinLat));
        return new LatLng(Math.toDegrees(Math.asin(sinLat)),
                Math.toDegrees(fromLng + dLng));
    }

    /**
     * Returns the location of origin when provided with a LatLng destination,
     * meters travelled and original heading. Headings are expressed in degrees
     * clockwise from North. This function returns null when no solution is
     * available.
     * 
     * @param to
     *            The destination LatLng.
     * @param distance
     *            The distance travelled, in meters.
     * @param heading
     *            The heading in degrees clockwise from north.
     */
    public static LatLng computeOffsetOrigin(final LatLng to, double distance,
            double heading) {
        heading = Math.toRadians(heading);
        distance /= MathUtil.EARTH_RADIUS;
        // http://lists.maptools.org/pipermail/proj/2008-October/003939.html
        final double n1 = Math.cos(distance);
        final double n2 = Math.sin(distance) * Math.cos(heading);
        final double n3 = Math.sin(distance) * Math.sin(heading);
        final double n4 = Math.sin(Math.toRadians(to.latitude));
        // There are two solutions for b. b = n2 * n4 +/- sqrt(), one solution
        // results
        // in the latitude outside the [-90, 90] range. We first try one
        // solution and
        // back off to the other if we are outside that range.
        final double n12 = n1 * n1;
        final double discriminant = ((n2 * n2 * n12) + (n12 * n12))
                - (n12 * n4 * n4);
        if (discriminant < 0) {
            // No real solution which would make sense in LatLng-space.
            return null;
        }
        double b = (n2 * n4) + Math.sqrt(discriminant);
        b /= (n1 * n1) + (n2 * n2);
        final double a = (n4 - (n2 * b)) / n1;
        double fromLatRadians = Math.atan2(a, b);
        if ((fromLatRadians < (-Math.PI / 2))
                || (fromLatRadians > (Math.PI / 2))) {
            b = (n2 * n4) - Math.sqrt(discriminant);
            b /= (n1 * n1) + (n2 * n2);
            fromLatRadians = Math.atan2(a, b);
        }
        if ((fromLatRadians < (-Math.PI / 2))
                || (fromLatRadians > (Math.PI / 2))) {
            // No solution which would make sense in LatLng-space.
            return null;
        }
        final double fromLngRadians = Math.toRadians(to.longitude)
                - Math.atan2(
                        n3,
                        (n1 * Math.cos(fromLatRadians))
                                - (n2 * Math.sin(fromLatRadians)));
        return new LatLng(Math.toDegrees(fromLatRadians),
                Math.toDegrees(fromLngRadians));
    }

    /**
     * Returns the signed area of a closed path on Earth. The sign of the area
     * may be used to determine the orientation of the path. "inside" is the
     * surface that does not contain the South Pole.
     * 
     * @param path
     *            A closed path.
     * @return The loop's area in square meters.
     */
    public static double computeSignedArea(final List<LatLng> path) {
        return SphericalUtil.computeSignedArea(path, MathUtil.EARTH_RADIUS);
    }

    /**
     * Returns the signed area of a closed path on a sphere of given radius. The
     * computed area uses the same units as the radius squared. Used by
     * SphericalUtilTest.
     */
    static double computeSignedArea(final List<LatLng> path, final double radius) {
        final int size = path.size();
        if (size < 3) {
            return 0;
        }
        double total = 0;
        final LatLng prev = path.get(size - 1);
        double prevTanLat = Math.tan(((Math.PI / 2) - Math
                .toRadians(prev.latitude)) / 2);
        double prevLng = Math.toRadians(prev.longitude);
        // For each edge, accumulate the signed area of the triangle formed by
        // the North Pole
        // and that edge ("polar triangle").
        for (final LatLng point : path) {
            final double tanLat = Math.tan(((Math.PI / 2) - Math
                    .toRadians(point.latitude)) / 2);
            final double lng = Math.toRadians(point.longitude);
            total += SphericalUtil.polarTriangleArea(tanLat, lng, prevTanLat,
                    prevLng);
            prevTanLat = tanLat;
            prevLng = lng;
        }
        return total * (radius * radius);
    }

    /**
     * Returns distance on the unit sphere; the arguments are in radians.
     */
    private static double distanceRadians(final double lat1, final double lng1,
            final double lat2, final double lng2) {
        return MathUtil.arcHav(MathUtil.havDistance(lat1, lat2, lng1 - lng2));
    }

    /**
     * Returns the LatLng which lies the given fraction of the way between the
     * origin LatLng and the destination LatLng.
     * 
     * @param from
     *            The LatLng from which to start.
     * @param to
     *            The LatLng toward which to travel.
     * @param fraction
     *            A fraction of the distance to travel.
     * @return The interpolated LatLng.
     */
    public static LatLng interpolate(final LatLng from, final LatLng to,
            final double fraction) {
        // http://en.wikipedia.org/wiki/Slerp
        final double fromLat = Math.toRadians(from.latitude);
        final double fromLng = Math.toRadians(from.longitude);
        final double toLat = Math.toRadians(to.latitude);
        final double toLng = Math.toRadians(to.longitude);
        final double cosFromLat = Math.cos(fromLat);
        final double cosToLat = Math.cos(toLat);

        // Computes Spherical interpolation coefficients.
        final double angle = SphericalUtil.computeAngleBetween(from, to);
        final double sinAngle = Math.sin(angle);
        if (sinAngle < 1E-6) {
            return from;
        }
        final double a = Math.sin((1 - fraction) * angle) / sinAngle;
        final double b = Math.sin(fraction * angle) / sinAngle;

        // Converts from polar to vector and interpolate.
        final double x = (a * cosFromLat * Math.cos(fromLng))
                + (b * cosToLat * Math.cos(toLng));
        final double y = (a * cosFromLat * Math.sin(fromLng))
                + (b * cosToLat * Math.sin(toLng));
        final double z = (a * Math.sin(fromLat)) + (b * Math.sin(toLat));

        // Converts interpolated vector back to polar.
        final double lat = Math.atan2(z, Math.sqrt((x * x) + (y * y)));
        final double lng = Math.atan2(y, x);
        return new LatLng(Math.toDegrees(lat), Math.toDegrees(lng));
    }

    /**
     * Returns the non-negative remainder of x / m.
     * 
     * @param x
     *            The operand.
     * @param m
     *            The modulus.
     */
    static double mod(final double x, final double m) {
        return ((x % m) + m) % m;
    }

    /**
     * Returns the signed area of a triangle which has North Pole as a vertex.
     * Formula derived from
     * "Area of a spherical triangle given two edges and the included angle" as
     * per "Spherical Trigonometry" by Todhunter, page 71, section 103, point 2.
     * See http://books.google.com/books?id=3uBHAAAAIAAJ&pg=PA71 The arguments
     * named "tan" are tan((pi/2 - latitude)/2).
     */
    private static double polarTriangleArea(final double tan1,
            final double lng1, final double tan2, final double lng2) {
        final double deltaLng = lng1 - lng2;
        final double t = tan1 * tan2;
        return 2 * Math.atan2(t * Math.sin(deltaLng),
                1 + (t * Math.cos(deltaLng)));
    }

    /**
     * Wraps the given value into the inclusive-exclusive interval between min
     * and max.
     * 
     * @param n
     *            The value to wrap.
     * @param min
     *            The minimum.
     * @param max
     *            The maximum.
     */
    static double wrap(final double n, final double min, final double max) {
        return ((n >= min) && (n < max)) ? n : (SphericalUtil.mod(n - min, max
                - min) + min);
    }

    private SphericalUtil() {
    }
}
